package com.sheng.leetcode.year2022.month09.day28;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/09/28
 *<p>
 * 面试题 17.09. 第 k 个数<p>
 *<p>
 * 有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。<p>
 * 注意，不是必须有这些素因子，而是必须不包含其他的素因子。<p>
 * 例如，前几个数按顺序应该是 1，3，5，7，9，15，21。<p>
 *<p>
 * 示例 1:<p>
 * 输入: k = 5<p>
 * 输出: 9<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/get-kth-magic-number-lcci">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCodeGetKthMagicNumber {

    @Test
    public void test01() {
        int k = 5;
        System.out.println(new Solution().getKthMagicNumber(k));
    }
}
class Solution {
    public int getKthMagicNumber(int k) {
        /**
         * 找下数字规律：
         * 1        3        5        7        9        15        21        25        27        35        45        49        63        75        81
         * 1*1      1*3      1*5      1*7      3*3      3*5       3*7       5*5       3*3*3     3*5       3*3*5     7*7       3*3*7     3*5*5     3*3*3*3
         * 105      135      147      175      189      225       245       315       343       375       441
         * 3*5*7    3*3*3*5  3*7*7    5*5*7    3*3*3*7  3*3*5*5   5*7*7     3*3*5*7   7*7*7     3*5*5*5   3*3*7*7
         */
        // 多路归并
        int[] ans = new int[k + 1];
        ans[1] = 1;
        for (int i3 = 1, i5 = 1, i7 = 1, idx = 2; idx <= k; idx++) {
            int a = ans[i3] * 3, b = ans[i5] * 5, c = ans[i7] * 7;
            int min = Math.min(a, Math.min(b, c));
            if (min == a) {
                i3++;
            }
            if (min == b) {
                i5++;
            }
            if (min == c) {
                i7++;
            }
            ans[idx] = min;
        }
        return ans[k];
    }
}
